﻿//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
//升序
class Solution
{
	int tmp[50010];
public:
	int reversePairs(vector<int>& nums)
	{
		return mergeSort(nums, 0, nums.size() - 1);
	}
	int mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return 0;
		int ret = 0;
		// 1. 找中间点，将数组分成两部分
		int mid = (left + right) >> 1;
		// [left, mid][mid + 1, right]
		// 2. 左边的个数 + 排序 + 右边的个数 + 排序
		ret += mergeSort(nums, left, mid);
		ret += mergeSort(nums, mid + 1, right);
		// 3. ⼀左⼀右的个数
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right) // 升序的时候
		{
			if (nums[cur1] <= nums[cur2])
			{
				tmp[i++] = nums[cur1++];
			}
			else
			{
				ret += mid - cur1 + 1;
				tmp[i++] = nums[cur2++];
			}
		}
		// 4. 处理⼀下排序
		while (cur1 <= mid) tmp[i++] = nums[cur1++];
		while (cur2 <= right) tmp[i++] = nums[cur2++];
		for (int j = left; j <= right; j++)
			nums[j] = tmp[j - left];
		return ret;
	}
};

//降序
class Solution {
public:
	vector<int> tmp;
	void merge(vector<int>& record, int left, int right, int& ret)
	{
		if (left >= right)return;
		int mid = (left + right) >> 1;
		merge(record, left, mid, ret);
		merge(record, mid + 1, right, ret);

		//寻找逆序对 + 合并
		int posLeft = left, posRight = mid + 1, pos = 0;
		while (posLeft <= mid && posRight <= right) {
			if (record[posLeft] > record[posRight]) {
				ret += right - posRight + 1;
				tmp[pos++] = record[posLeft++];
			}
			else tmp[pos++] = record[posRight++];
		}
		while (posLeft <= mid)tmp[pos++] = record[posLeft++];
		while (posRight <= right)tmp[pos++] = record[posRight++];

		for (int i = left; i <= right; i++)record[i] = tmp[i - left];
	}
	int reversePairs(vector<int>& record) {
		tmp.resize(record.size());
		int ret = 0;
		merge(record, 0, record.size() - 1, ret);
		return ret;
	}
};